#include <cstdio>
#include <cstring>
#define MAXN 10000
#define INF 100000000

int edge[MAXN][MAXN];
int p,q;
int u,v,w;
int sum;
int dist[MAXN];
int s[MAXN];

void dijkstra()
{
    for (int i=1; i<=p; i++){
        dist[i]=edge[1][i];
        s[i]=0;
       }
    s[1]=1;
    dist[1]=0;
    int j=1,min=INF;
    for (int k=2;k<=p;k++)
    {
        for (int i=1;i<=p;i++)
        {
            if (s[i]!=1 && dist[i]<min)
            {
                j=i;
                min=dist[i];
             }
        }
        s[j]=1;

        for (int i=1;i<=p;i++)
        {
            if (s[i]==0 && edge[j][i]<INF && dist[i]>dist[j]+edge[j][i])
                dist[i]=dist[j]+edge[j][i];
        }
    }
    for(int i=1;i<=p;i++)
    {
        if (dist[i]!=INF)
            sum+=dist[i];
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while ( t-- )
    {
        scanf("%d%d",&p,&q);
        memset(edge,INF,sizeof(edge));
        for (int i=1; i<=p; i++)
            edge[i][i]=0;
        while ( q-- )
        {
            scanf("%d%d%d",&u,&v,&w);
            edge[u][v]=w;
        }
        sum=0;
        dijkstra();
        for (int i=1;i<=p;i++)
            for (int j=1;j<=p;j++)
            {
                int tmp;
                tmp=edge[i][j];
                edge[i][j]=edge[j][i];
                edge[j][i]=tmp;
            }
        dijkstra();
        printf("%d\n",sum);
    }
    return 0;
}
